package com.xw.class08;

import java.util.Arrays;

/**
 * @author: xw
 * @create: 2023/5/17 14:25
 * @description: 桶排序之基数排序
 */
public class Code04_RadixSort {

    public static void radixSort(int[] arr){
        if(null == arr || arr.length < 2){
            return;
        }
        radixSort(arr, 0, arr.length-1,maxBit(arr));
    }

    /**
     * 计算出arr数组需要进几次桶才能排好序
     * @param arr
     * @return
     */
    public static int maxBit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max,arr[i]);
        }
        int res = 0;
        while(max != 0){
            res++;
            max /= 10;
        }
        return res;

    }

    /**  int[] arr = {88,226,2,98,146.10,52,7,3};
     * 大致思路：根据最大的数字有几位 判断有几次外层循环 ,此时外层需要三次for循环
     *  遍历个位：
     *     第一个for 循环 ：记录对应位上的数字有几个，比如个位数字为1的有4个，即count数组，如：int[] count = {1,0,2,1,0,0,2,1,2,0}
     *     第二个for循环：将count数组进行前缀和累加,该数组的含义为小于等于0的数有count[0]个  。int[] count = {1,1,3,4,4,4,6,7,9}
     *     第三个for循环：将原数组从右往左遍历，看对应位上的count数组上的值，确定排序顺序，放入help数组后对count数组的值--。
     *     例如 小于等于3数有4个，那么第一个数3，的范围就是0-3，又是第一个，所以 3对应help数组的3位置，然后int[] count = {1,1,3,3,4,4,6,7,9}
     *     以此类推，第一次遍历完辅助数组中数应该是{10,2,52,3,226,146,7,88,98}
     *     第四个for循环：将help数组赋值给原数组
     * 遍历十位....
     *
     * @param arr
     * @param L
     * @param R
     * @param digit
     */
    public static void radixSort(int[] arr, int L, int R, int digit) {
        final int radix = 10;
        int i = 0, j = 0;
        // 有多少个数准备多少个辅助空间
        int[] help = new int[R - L + 1];
        for(int d = 1; d<=digit; d++){
            // 10个空间
            // count[0] 当前位(d位)是0的数字有多少个
            // count[1] 当前位(d位)是(0和1)的数字有多少个
            // count[2] 当前位(d位)是(0、1和2)的数字有多少个
            // count[i] 当前位(d位)是(0~i)的数字有多少个
            int[] count = new int[radix];
            for (i = L; i <= R; i++){
                j = getDigit(arr[i], d);
                count[j]++;
            }
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            for(i = R; i >=L; i--){
                j = getDigit(arr[i], d);
                help[count[j] - 1] = arr[i];
                count[j]--;
            }
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = help[j];
            }

        }
    }

    /**
     * 返回x对应的d位上的数字
     * @param x
     * @param d
     * @return
     */
    public static int getDigit(int x, int d) {
        return (x/((int)Math.pow(10,d-1))) % 10 ;
    }

    // for test
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100000;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            radixSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        radixSort(arr);
        printArray(arr);

    }
}
